<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>二叉树</title>
  </head>
  <body>
  <script>
  var LINK = 0;
  var THREAD = 1;

  function BinaryThreadTree_inOrder(data, leftChild, rightChild) {
      this.data = data;
      this.leftChild = leftChild || null;
      this.rightChild = rightChild || null;
      // 左右标记
      this.leftTag = this.rightTag = undefined;
  }
  BinaryThreadTree_inOrder.prototype = {
      constructor: BinaryThreadTree_inOrder,
      // 中序线索二叉树的遍历
      inOrderTraverse_thread: function (visit) {
          var p = this.leftChild;

          while (p != this) {
              while (p.leftTag === LINK) p = p.leftChild;

              if (visit(p.data) === false) return;

              while (p.rightTag == THREAD && p.rightChild != this) {
                  p = p.rightChild;
                  visit(p.data);
              }
              p = p.rightChild;
          }
      },
      // 中序线索化
      inOrderThreading: function () {
          return inOrderThreading(this);
      },
      // 在当前结点插入子树x，p代表当前结点
      insertSubTree: function (xTree) {
          var s, q;
          // x作为p的左子树
          if (this.leftTag === THREAD) {
              s = this.leftChild; // s为p的前驱
              this.leftTag = LINK;
              this.leftChild = xTree;
              q = xTree;

              while (q.leftChild && q.leftTag === LINK) q = q.leftChild;
              // 找到子树中的最左结点，并修改其前驱指向s
              q.leftChild = s;
              xTree.rightTag = THREAD;
              // x的后继指向p
              xTree.rightChild = this;
          }
          // x作为p的右子树
          else if (this.rightTag === THREAD) {
              // s为p的后继
              s = this.rightChild;
              this.rightTag = LINK;
              this.rightChild = xTree;
              q = xTree;

              while (q.leftChild && q.leftTag === LINK) q = q.leftChild;
              // 找到子树中的最左结点，并修改其前驱指向p
              q.leftChild = this;
              xTree.rightTag = THREAD;
              // x的后继指向p的后继
              xTree.rightChild = s;
          }
          // x作为p的左子树，p的左子树作为x的右子树
          else {
              s = this.leftChild;
              var t = s;

              while (t.leftChild && t.leftTag === LINK) t = t.leftChild;
              // 找到p的左子树的最左结点t和前驱u
              var u = t.leftChild;
              this.leftChild = xTree;
              xTree.rightTag = LINK;
              // x作为p的左子树，p的左子树作为x的右子树
              xTree.rightChild = s;
              t.leftChild = xTree;
              q = xTree;

              while (q.leftChild && q.leftTag === LINK) q = q.leftChild;
              // 找到子树中的最左结点，并修改其前驱指向u
              q.leftChild = u;
          }
      }
  };

  // 二叉树中序线索化
  function inOrderThreading(tree) {
      var threadTree = new BinaryThreadTree();
      threadTree.leftTag = LINK;
      threadTree.rightTag = THREAD;
      // 右指针回指
      threadTree.rightChild = threadTree;

      var pre;
      // 若二叉树为空，左指针回指
      if (!tree) threadTree.leftChild = threadTree;
      else {
          threadTree.leftChild = tree;
          pre = threadTree;
          inThreading(tree);  // 中序遍历进行中序线索化
          // 最后一个结点线索化
          pre.rightChild = threadTree;
          pre.rightTag = THREAD;
          threadTree.rightChild = pre;
      }

      return threadTree;

      function inThreading(p) {
          if (!p) return;

          inThreading(p.leftChild);   // 左子树线索化
          // 前驱线索
          if (!p.leftChild) {
              p.leftTag = THREAD;
              p.leftChild = pre;
          }
          // 后继线索
          if (!pre.rightChild) {
              pre.rightTag = THREAD;
              pre.rightChild = p;
          }
          pre = p;
          inThreading(p.rightChild);  // 右子树线索化
      }
  }
  </script>

  </body>
</html>
